package com.linchong.dynamicprogramming.hard;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @author linchong
 * @version 1.0
 * @Date: 2020-11-20 12:15
 * @Description: RussianDollEnvelopes$354-俄罗斯套娃信封问题-https://leetcode-cn.com/problems/russian-doll-envelopes/
 */
public class RussianDollEnvelopes {

	/**
	 *
	 * 给定一些标记了宽度和高度的信封，宽度和高度以整数对形式 (w, h) 出现。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
	 *
	 * 请计算最多能有多少个信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
	 *
	 * 说明:
	 * 不允许旋转信封。
	 *
	 * 示例:
	 *
	 * 输入: envelopes = [[5,4],[6,4],[6,7],[2,3]]
	 * 输出: 3
	 * 解释: 最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。
	 *
	 * 来源：力扣（LeetCode）
	 * 链接：https://leetcode-cn.com/problems/russian-doll-envelopes
	 *
	 * 【分析】
	 *  可能出现一个信封A能放入信封B和信封C,但是信封B和信封C互相不能放入
	 *
	 *  “二维的题经常先按一维的考虑”
	 *
	 *  将所有的信封按照长度一维进行排序：E0,E1,E2...En-1
	 *
	 *  如此，如果信封i能够放入到信封j中，一定有i<j
	 *
	 *  排序后，如果一个信封Ej是最外层的信封，那么它里面的第一层信封Ei一定满足i<j
	 *
	 *  step 1 确定状态：
	 *      最后一步：设最优策略中最后一个信封，即最外层的信封，是Ei
	 *
	 *      考虑次外层的信封是那个
	 *          一定是某个Ej,i<j
	 *      最优策略里，以Ei为最外层信封的嵌套层数也一定是最多的
	 *
	 *      子问题：以Ei为最外层信封时最多的嵌套成熟，
	 *          需要知道以Ej为最外层信封时最多的嵌套层数（j<i）
	 *
	 *      状态：设f[i]表示以Ei为最外层信封时最多嵌套的层数
	 *
	 *  step 2 转移方程：
	 *      f[i] = max{1,f[j]+1|Ej能放入到Ei中}
	 *                 只使用Ei这一个信封  以Ej为外层信封时最多的嵌套层数+Ei
	 *  step 3 初始条件和边界情况：
	 *      设f[i]表示以Ei为最外层信封时最多嵌套的层数
	 *          f[i] = max{1,f[j]+1|Ej能放入到Ei中，j<i}
	 *
	 *       无初始条件
	 *       需要先把所有信封按照长度进行排序
	 *
	 *  step 4 计算顺序
	 *      f[0],f[1],...,f[n-1]
	 *
	 *      时间复杂度O(N^2),空间复杂度O(N)
	 *  todo: nlogn
	 *      处理相同长度的情况问题，将小宽度放前面
	 *
	 *
	 */
	public int maxEnvelopes(int[][] envelopes) {
		if(envelopes == null || envelopes.length == 0){
			return 0;
		}

		Arrays.sort(envelopes, new Comparator<int[]>() {

			@Override
			public int compare(int[] o1, int[] o2) {
				if(o1[0] == o2[0]){
					return o1[1]-o2[1];
				}else{
					return o1[0]-o2[0];
				}
			}
		});
		int n = envelopes.length;
		int[] f = new int[n];
		int i,j,res=0;

		for (i = 0; i < n; i++) {
			f[i] = 1;
			for (j = 0; j < i; j++) {
				// 长度，宽度均小
				if(envelopes[j][0]<envelopes[i][0]&&envelopes[j][1]<envelopes[i][1]){
					f[i] = Math.max(f[i],f[j]+1);
				}
			}
			res = Math.max(res,f[i]);

		}
		return res;
	}
	public static void main(String[] args) {
		int[][] envelopes = {{5,4},{6,4},{6,7},{2,3}};
		RussianDollEnvelopes instance = new RussianDollEnvelopes();
		System.out.println(instance.maxEnvelopes(envelopes));
	}
}
